package problem148_Sort_List;

import problem82_Remove_Duplicates_from_Sorted_List2.ListNode;

public class Solution {
	 public ListNode sortList(ListNode head) {
	        if(head==null||head.next==null)
	        	return head;
	        ListNode head2=getMidAndCut(head);
	        ListNode sort1=sortList(head);
	        ListNode sort2=sortList(head2);
	        return mergerTwoSortedLists(sort1,sort2);
	 }
	 
	 private ListNode mergerTwoSortedLists(ListNode node1,ListNode node2){
		 ListNode dummy=new ListNode(-1);
		 ListNode tail=dummy;
		 while(node1!=null&&node2!=null){
			 if(node1.val<node2.val){
				 tail.next=node1;
				 node1=node1.next;
			 }else{
				 tail.next=node2;
				 node2=node2.next;
			 }
			 tail=tail.next;
		 }
		 tail.next=(node1==null?node2:node1);
		 return dummy.next;
	 }
	 
	 private ListNode getMidAndCut(ListNode head){
		 ListNode slow=head,fast=head,pre=head;
		 while(fast!=null&&fast.next!=null){
			 fast=fast.next.next;
			 pre=slow;
			 slow=slow.next;
		 }
		 pre.next=null;
		 return slow;
	 }
}
